import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] distances = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
        //初始化distance
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(mat[i][j] == 0) {
                    distances[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
                else distances[i][j] = -1;
            }
        }
        while(!queue.isEmpty()){
             int sz = queue.size();
             for(int i = 0; i < sz; i++){
                 int[] poll = queue.poll();
                 //拿到当前位置元素到最近的 0 的距离
                 int distance = distances[poll[0]][poll[1]];
                 for(int k = 0; k < 4; k++){
                     int x = dx[k] + poll[0];
                     int y = dy[k] + poll[1];
                     if(x >= 0 && x < n && y >= 0 && y < m && distances[x][y] == -1){
                         queue.offer(new int[]{x, y});
                         distances[x][y] = distance + 1;
                     }
                 }
             }
        }

        return distances;
    }
}